<html>
<title>Viewer's Prize in F-TV</title>
<body>
<center>
<h1>Problem E</h1>
<h1>Viewer's Prize in F-TV</h1>
</center>

<h2>Problem</h2>
<p>The successful launching of third-generation (3G) mobile phone by the Japanese giant DoCoMo marked the beginning of an era in real-time multi-media inter-net communications at affordable cost. The F-TV or the Future TV has the reputation to venture into innovative TV programs that might attract large number of viewers in near future. In order to remain ahead in the race to have the largest number of viewers during a prime time slot in comparison to other TV channels, the management of F-TV plans to produce a TV program that will provide a large number of viewers with an opportunity to chat with a celebrity either in person or in real-time virtually using mobile phones and get cash prizes in the process.
<p>The planned TV program consists in having a celebrity on each show as the anchor of the chat show and a selected number of viewers as ��real�� participants. Any number of remote viewers may also join the program during the show as ��virtual�� participants using their 3G mobile phones from anywhere in the world. Each participant, male or female, real or virtual, is enrolled for the show and is given a unique token serial number on first come first served basis. Towards the end of the show the anchor runs a computer program that selects participants from among the enrolled participants and announces cash prizes for the selected participants. There is a possibility that no participant is selected for a prize; in such a case the anchor announces the decision accordingly.
<p>The computer program selects the participants to get prizes in a simple way. Let n be the total number of participants, real or virtual. Each participant is given a token serial number p, p=1, 2�� n. Let xp, be equal to 0 if the participant having the token serial number p, is female, otherwise xp is equal to 1. The input to the program is the string x=( x1, x2, �� xn ) of length n on the alphabet { 0, 1}. The program finds the longest palindromes contained in x ( i.e. the longest sub-strings made up of elements of x each of which reads the same backward as forward). Let there be k such palindromes and let U be the union of all these palindromes. The program deletes U from x. It repeats the process with the reduced string x successively until there is no palindrome of length 3 or more. Finally it finds the elements of x, if any, which are retained in the process.
<p>For example, let n=37 and x=( 0110 1110 1101 1011 0111 0101 1101 0010 0101 1 ) where the elements of x are written in groups of four followed by a blank character, for easy readability. The sub-string (x3,..x22)=( 10 1110 1101 1011 0111 01 ) is of length 20 and is the longest palindromes in x. If this sub-string is deleted then the string x is reduced to ( x1, x2, x23, x24,... x37 ) with elements ( 0101 1101 0010 0101 1 ) which when reduced further gives ( x1, x2, x23,x24 ) with elements ( 0101 ). Finally, since the longest palindromes in ( 0101 ) are ( 010 ) and (101) , each of which is of length 3 and their union is the entire string under consideration, all the four elements are deleted. Hence, no element of x is selected.

<h2>Input</h2>
<p>The input may contain multiple test cases.
<p>For each test case, the first line contains two integers the case number c and the length n of the given string. The string x is given in one or more lines in groups of four elements separated by a blank character; the last group in the string may contain less than four elements. The string is terminated with the character $ which is not considered as a part of the string.
<p>The entire input set terminates with an input 0 for c.

<h2>Output</h2>
<p>For each test case in the input, print the test case number c and the number k of participants selected for the prize. In next k lines, print the token serial numbers of the participants selected for the prize in ascending order.
<p>Print a blank line before printing the output of the next test case.

<h2>Sample Input</h2>
<pre>
1 37
0110 1110 1101 1011 0111 0101 1101 0010 0101 1 $
2 62
1011 0001 1110 1010 1111 0010 1010 0111 1101 1010 0110 0011 0110 0011 0111 10 $
0
</pre>

<h2>Output for the Sample Input</h2>
<pre>
1 0
2 1
1
</pre>
<hr>
<b>Problem Source: </b>ACM/ICPC Regional Contest Asia-Kanpur 2001. Problem E. Viewer's Prize in F-TV<br>
<b>Problem Archive: </b>None<br>
</body>
</html>